11116 - Babel towers/11116.2.cpp

   1 /*
   2  Problem: 11116 - Babel towers
   3  (From the UVa Online Judge)
   4
   5  Author: Andrés Mejía-Posada
   6  Date: April 20/2008
   7 */
   8
   9 #include <iostream>
  10 #include <iomanip>
  11 #include <cmath>
  12 #include <algorithm>
  13 #include <vector>
  14
  15 using namespace std;
  16
  17 const double EPS = 10E-9;
  18
  19 struct disc{
  20   double x, y, r;
  21   disc(){}
  22   disc(double X, double Y, double R) : x(X), y(Y), r(R){}
  23 };
  24
  25 //Represents a mass "m" centered at point ("x", "y")
  26 struct center{
  27   double x, y, m;
  28   center(){}
  29   center(double X, double Y, double M) : x(X), y(Y), m(M){}
  30   center &operator = (const center &b){
  31     x = b.x;
  32     y = b.y;
  33     m = b.m;
  34     return *this;
  35   }
  36 };
  37
  38
  39 //Returns the new mass formed by combining both masses "a" and "b" into a puntual mass.
  40 center operator | (const center &a, const center &b){
  41   center r;
  42   r.x = (a.x * a.m + b.x * b.m) / (a.m + b.m);
  43   r.y = (a.y * a.m + b.y * b.m) / (a.m + b.m);
  44   r.m = a.m + b.m;
  45   return r;
  46 }
  47
  48 //For debugging
  49 ostream& operator<<( ostream& out, const center &c) {
  50   out << setprecision(2) << "(" << c.x << ", " << c.y << ", " << c.m << ")";
  51   return out;
  52 }
  53
  54 //For debugging
  55 ostream& operator<<( ostream& out, const disc &c) {
  56   out << setprecision(2) << "(" << c.x << ", " << c.y << ", " << c.r << ")";
  57   return out;
  58 }
  59
  60
  61 //True if the center of mass "C" is outside of the base of disc "D"
  62 inline bool outside(const center &c, const disc &d){
  63   return fabs((c.x-d.x)*(c.x-d.x) + (c.y-d.y)*(c.y-d.y)) >  d.r*d.r - EPS;
  64 }
  65
  66 int main(){
  67   int n;
  68   while (cin >> n && n){
  69
  70     vector<disc> d(n);
  71     for (int i=0; i<n; ++i){
  72       double x, y, r;
  73       cin >> x >> y >> r;
  74       d[i] = disc(x, y, r);
  75
  76     }
  77
  78     int k;
  79     bool ok = true;
  80     for (int j=1; j < n && ok; ++j){
  81       center c(d[j].x, d[j].y, d[j].r * d[j].r);
  82
  83       for (int i=j-1; i >= 0 && ok; --i){
  84         if (outside(c, d[i])){
  85           ok = false;
  86           k = j;
  87         }
  88         c = c | center(d[i].x, d[i].y, d[i].r*d[i].r);
  89       }
  90     }
  91
  92     cout << (ok?"F":"Unf") << "easible";
  93     if (!ok) cout << " " << k;
  94     cout << endl;
  95
  96   }
  97   return 0;
  98 }